Shipping companies are faced with moving multiple packages between multiple locations. Accordingly, it is important that the shipping companies strive to schedule the movement of packages in an effective and efficient manner. For example, a shipping company may have packages at 11 different locations for delivery to 20 different destinations. Additionally, the packages can have varying delivery schedules and the shipping company can have a defined number of vehicles. Accordingly, the shipping company must determine which packages can be transported on which vehicle and determine the sequence of stops that each vehicle must make in order to deliver the packages to their corresponding destination on time.
The task of determining which packages to transport on which vehicle and determining the sequence of stops that each vehicle must make can be complicated, difficult, and time consuming, especially when there is a large number of packages and vehicles. One method that shipping companies use to perform this task is to select a “seed” package that is being shipped from one location to another based on some criteria (e.g., the heaviest package at a location) and to schedule the package for delivery on a first vehicle. Additional packages are then scheduled on the first vehicle for delivery at the same or a different location. The shipping company then selects another “seed” package and schedules it for delivery on a second vehicle. Additional packages are then scheduled on the second vehicle for delivery at the same or a different location, and so on, until all of the packages are scheduled for delivery. A drawback of this process is that once a seed package is selected and scheduled on a vehicle, future seed package and vehicle selections are limited to the remaining packages and vehicles. Accordingly, this process does not necessarily converge toward a low cost solution because early selections are blind to the consequences associated with subsequent selections and therefore, may eliminate lower cost solutions.
Even if a large number of combinations are tried (e.g., using a set of linear equations to predict the expense associated with each combination), the process is blind to the consequences associated with subsequent selections and there is no guarantee that the process will converge toward lower cost solutions. Furthermore, these processes generally do not account for real-world constraints and variables. For example, in many cases combinations are generated and tried, even though they are unrealistic or impractical. For instance, in many cases, these equations fail to take into account shipping restrictions (e.g., packages that must be placed in a refrigerated truck), mutually exclusive combinations, non-linear rate breaks for a large number of packages being shipped to a selected destination, etc.